ICPC Live Archive/3928 - Ballroom lights/ballroom.cpp

   1 #include <iostream>
   2 #include <cmath>
   3 #include <cstdio>
   4 #include <list>
   5 #include <utility>
   6 #include <cstdlib>
   7 #include <cassert>
   8 #include <complex>
   9
  10 #define forn(i, n) for (int i = 0; i < (n); i++)
  11 #define TOLERANCIA 1e-8
  12
  13 using namespace std;
  14
  15 struct MaybeDouble {
  16     long double valor;
  17     bool valido;
  18
  19     MaybeDouble(long double v, bool b): valor(v), valido(b) {};
  20 };
  21
  22 struct Vector {
  23     long double x;
  24     long double y;
  25
  26     Vector(long double xi, long double yi): x(xi), y(yi) {};
  27
  28     long double norma()  {
  29         return hypot(x, y);
  30     }
  31
  32     long double angulo() {
  33         return atan2(y, x);
  34     }
  35
  36 };
  37
  38 struct Columna {
  39     Vector posicion;
  40     long double radio;
  41
  42     Columna(long double x, long double y, long double r) : posicion(x,y), radio(r) {};
  43 };
  44
  45 typedef Vector Lampara;
  46 typedef pair<long double, long double> Intervalo;
  47 typedef pair<Vector, Vector> Segmento;
  48
  49
  50 inline long double largo(const Segmento& s) {
  51     return Vector(s.second.x - s.first.x, s.second.y - s.first.y).norma();
  52 }
  53
  54 inline long double largo(const Intervalo& i) {
  55     assert(i.first <= i.second);
  56     return i.second - i.first;
  57 }
  58
  59
  60 MaybeDouble intersect_segments(const Segmento& s1, const Segmento& s2) {
  61     Vector p1 = s1.first;
  62     Vector p2 = s1.second;
  63     Vector p3 = s2.first;
  64     Vector p4 = s2.second;
  65
  66     long double den = (p4.y-p3.y)*(p2.x-p1.x) - (p4.x-p3.x)*(p2.y-p1.y);
  67
  68     long double ua_num = (p4.x-p3.x)*(p1.y-p3.y) - (p4.y-p3.y)*(p1.x-p3.x);
  69     long double ub_num = (p2.x-p1.x)*(p1.y-p3.y) - (p2.y-p1.y)*(p1.x-p3.x);
  70
  71     if (fabs(den) < TOLERANCIA) {
  72         // Caso en que los segmentos son paralelos
  73         if (fabs(ua_num - ub_num) < TOLERANCIA && fabs(ub_num) < TOLERANCIA) {
  74             // Las rectas son coincidentes, esto no deberia ocurrir
  75             assert(false);
  76             return MaybeDouble((p1.norma() > p2.norma()? 0 : 1), true);
  77         }
  78         return MaybeDouble(0, false);
  79     }
  80
  81     if (ub_num/den >= 0) {
  82         return MaybeDouble(ua_num/den, true);
  83     }
  84     return MaybeDouble(0, false);
  85 }
  86
  87
  88 Intervalo interseccion_intervalos(const Intervalo& i1, const Intervalo& i2) {
  89
  90     long double d0 = max(i1.first, i2.first);
  91     long double d1 = min(i1.second, i2.second);
  92
  93     if (d1 < d0) {
  94         return Intervalo(0, 0);
  95     } else {
  96         return Intervalo(d0, d1);
  97     }
  98 }
  99
 100
 101 Intervalo rango_oscurecido(const Segmento& pared, const Lampara& lampara, const Columna& columna) {
 102     Vector bisectriz(columna.posicion.x - lampara.x, columna.posicion.y - lampara.y);
 103     long double p = asin(columna.radio/bisectriz.norma());
 104     long double alpha = bisectriz.angulo();
 105
 106     Vector d1(cos(alpha + p), sin(alpha + p));
 107     Vector d2(cos(alpha - p), sin(alpha - p));
 108
 109     MaybeDouble p1 = intersect_segments(pared, Segmento(lampara, Vector(lampara.x + d1.x, lampara.y + d1.y)));
 110     MaybeDouble p2 = intersect_segments(pared, Segmento(lampara, Vector(lampara.x + d2.x, lampara.y + d2.y)));
 111     printf("p1 = [%d, %Lf]\n", p1.valido, p1.valor);
 112     printf("p2 = [%d, %Lf]\n", p2.valido, p2.valor);
 113
 114
 115     long double unidad = largo(pared);
 116
 117     // Se sabe que los puntos de interseccion estan ordenados correctamente
 118     // porque el angulo de diferencia entre las semirectas es menor a 180,
 119     // entonces no es necesario chequearlo.
 120     Intervalo res;
 121
 122     if (!p1.valido) {
 123         if (!p2.valido) {
 124             return Intervalo(0, 0);
 125         } else {
 126             res = Intervalo(0, p2.valor);
 127         }
 128     } else {
 129         if (!p2.valido) {
 130             res = Intervalo(p1.valor, 1);
 131         } else {
 132             res = Intervalo(p1.valor, p2.valor);
 133         }
 134     }
 135
 136     res = interseccion_intervalos(res, Intervalo(0,1));
 137     printf("Shadow: [%Lf, %Lf]\n",res.first * unidad, res.second * unidad);
 138     return Intervalo(res.first * unidad, res.second * unidad);
 139 }
 140
 141 void invertir_rango(const list<Intervalo>& ints, long double fin, list<Intervalo>& out) {
 142
 143     if (!ints.size()) {
 144         out.push_back(Intervalo(0,fin));
 145         return;
 146     }
 147
 148
 149     list<Intervalo>::const_iterator it = ints.begin();
 150     if (it->first > 0) {
 151         out.push_back(Intervalo(0, it->first));
 152     }
 153
 154     it++;
 155
 156     list<Intervalo>::const_iterator itprev = ints.begin();
 157     while (it != ints.end()) {
 158         out.push_back(Intervalo(itprev->second, it->first));
 159         it++;
 160         itprev++;
 161     }
 162
 163     if (itprev->second < fin) {
 164         out.push_back(Intervalo(itprev->second, fin));
 165     }
 166 }
 167
 168
 169 void reduce_union(list<Intervalo>& l_o, list<Intervalo>& out) {
 170     // elimino repetidos para acelerar el sort
 171     list<Intervalo> l;
 172
 173     for (list<Intervalo>::const_iterator itcito = l_o.begin(); itcito != l_o.end(); itcito++) {
 174         if (itcito->first < itcito->second) {
 175             l.push_back(Intervalo(itcito->first, itcito->second));
 176         } else if (itcito->first > itcito->second) {
 177             assert(false);
 178         }
 179     }
 180
 181
 182     if (!l.size()) return;
 183
 184     l.sort();
 185
 186     list<Intervalo>::const_iterator it = l.begin();
 187     Intervalo cand = *it;
 188     Intervalo otro;
 189
 190     it++;
 191     while (it != l.end()) {
 192         otro = *it;
 193         if (otro.first < otro.second) {
 194             if (otro.first > cand.second) {
 195                 out.push_back(cand);
 196                 cand = otro;
 197             } else {
 198                 if (otro.second > cand.second) {
 199                     cand = Intervalo(cand.first, otro.second);
 200                 }
 201             }
 202         }
 203         it++;
 204     }
 205
 206     out.push_back(cand);
 207 }
 208
 209
 210 long double resolver(const list<Lampara>& lamparas, const list<Columna>& columnas, int max_x, int max_y) {
 211     list<Segmento> paredes;
 212     paredes.push_back(Segmento(Vector(0,0), Vector(0, max_y)));
 213     paredes.push_back(Segmento(Vector(0,max_y), Vector(max_x, max_y)));
 214     paredes.push_back(Segmento(Vector(max_x,max_y), Vector(max_x, 0)));
 215     paredes.push_back(Segmento(Vector(max_x,0), Vector(0, 0)));
 216
 217     long double total = 0;
 218
 219     for (list<Segmento>::iterator p = paredes.begin(); p != paredes.end(); p++) {
 220         list<Intervalo> luces_pared;
 221         for (list<Lampara>::const_iterator l = lamparas.begin(); l != lamparas.end(); l++) {
 222             list<Intervalo> zonas_tapadas;
 223             for (list<Columna>::const_iterator c = columnas.begin(); c != columnas.end(); c++) {
 224                 zonas_tapadas.push_back(rango_oscurecido(*p, *l, *c));
 225             }
 226
 227             list<Intervalo> tapadas_unidas;
 228             list<Intervalo> zona_iluminada;
 229
 230             reduce_union(zonas_tapadas, tapadas_unidas);
 231             invertir_rango(tapadas_unidas, largo(*p), zona_iluminada);
 232
 233             luces_pared.splice(luces_pared.end(), zona_iluminada);
 234         }
 235
 236         list<Intervalo> luces_pared_unidas;
 237         reduce_union(luces_pared, luces_pared_unidas);
 238
 239         for (list<Intervalo>::iterator it = luces_pared_unidas.begin(); it != luces_pared_unidas.end(); it++) {
 240             printf("Lit: [%Lf, %Lf]\n", it->first, it->second);
 241             total += largo(*it);
 242         }
 243     }
 244
 245     return total;
 246 }
 247
 248
 249 int main() {
 250
 251     int nl, nc, max_x, max_y;
 252
 253     for (;;) {
 254         scanf("%d %d %d %d", &nl, &nc, &max_x, &max_y);
 255
 256         if (!(nl || nc || max_x || max_y)) {
 257             break;
 258         }
 259
 260         list<Vector> lamparas;
 261         list<Columna> columnas;
 262
 263         int x, y, r;
 264
 265         forn(i, nl) {
 266             scanf("%d %d", &x, &y);
 267             lamparas.push_back(Lampara(x,y));
 268         }
 269
 270         forn(i, nc) {
 271             scanf("%d %d %d", &x, &y, &r);
 272             columnas.push_back(Columna(x, y, r));
 273         }
 274
 275         printf("%.4Lf\n", resolver(lamparas, columnas, max_x, max_y));
 276     }
 277 }